Direct sequence spread spectrum (DSSS) is a method that is used in the transmission of digital information to a receiver. In this technique, the data signal is multiplied by a higher rate spreading sequence, also referred to as a spreading code, to form a wideband signal. This process is known as spreading. Typically, the spreading code is a pseudo-random, also known as pseudo-noise (PN), sequence that is generated at a DSSS transmitter using a spreading generator such as a linear feedback shift register (LFSR).
To recover the data signal, a DSSS receiver must determine the code phase of the received signal and generate a local replica of the spreading sequence. The term “code phase” of a spreading sequence or code refers to a specific position within the spreading sequence corresponding to the received signals. The local replica of the spreading code must be properly aligned with the received signal so that the result of the multiplication of the local replica and the received signal results in the data signal. Determining the code phase of the spreading code for a received signal is known as code phase acquisition, or spreading code acquisition.
A technique wherein the full spectrum of the DSSS signal is shared among a number of users, wherein each of which is assigned a unique spreading code, is known as the direct sequence code division multiple access (DS-CDMA). Commercial applications of DS-CDMA include cellular phone systems. Typically, a conventional DS-CDMA receiver of a commercial CDMA communication system has information about the spreading code of the transmitted spread spectrum signal, so it can successfully de-spread the received signal to obtain the transmitted data after a relatively straightforward code-signal synchronization procedure. However, sometimes there is a need for blind spreading code acquisition, when the receiver has minimal or no information about the spreading code of the received DSSS signal and its code phase. One example is a communication system surveillance or monitoring, wherein the task may be to detect the presence of on-going communications by a third party. In such cases, the receiver lacks the information about the phase of the spreading code, which should be “blindly” recovered for the detection to be successful.
Several prior-art techniques for acquisition of PN sequences, which are generated using a spreading generator of a known structure, utilize a local version of the spreading code and repeatedly correlate the spreading sequence with one or more positions of the received signal until proper alignment is detected. For long PN sequences attempting all positions would be impractical due to the required number of correlations. If no information is available at the receiver about the code phase, the average acquisition time increases with the period of the spreading code. Using a long spreading sequence makes it difficult for a casual eavesdropper to find the correct code phase by correlating with the received signal because the number of possible starting positions that require testing make the correlation techniques impractical.
In the cellular standards “Physical Layer Standard for cdma2000 Spread Spectrum Systems Rev C. Jul. 23, 2004 3 GPP2 C.S0002-C Version 2” and “cdma2000 High Rate Packet Data Air Interface Specification Version 3.0 September 2006 3GPP2 C.S.0024-A”, a long PN code is used to allow for a large number of addressable users. The effective period of the spreading code is 242-1 chips. At a typical chip rate of 1.2288 Mega-chips per second (Mchips/sec), the spreading code would repeat itself in 41 days, making the blind search for “best correlation” impractical.
One known approach to blind code phase acquisition is to treat the spreading code acquisition problem as a decoding problem. In many cases, the spreading code used in a CDMA system is generated by linear functions operating on the output of a linear system. The structure of the linear system defines a linear code, and conventional methods of decoding of linear block codes can be applied to the spreading code acquisition problem.
A block code is characterized by a doublet (n,k) where n symbols form a code word based on k symbols of information. A valid sequence of n symbols for a block code (n, k) is called a code word, and n and k are hereafter referred to as respectively the length and the dimension of the block code. Since there can be many more possible combinations of n symbols in a block of length n than possible datasets of length k, not all combinations of n symbols can be a valid code word, which assists in decoding.
A block code (n, k) is called a linear block code if the sum of each two code words also is a code word. For binary codes, binary addition is assumed to be an exclusive ‘OR’ (XOR) operation. A parity check matrix, H, of a linear block code (n,k) is any (n−k)×n matrix of rank (n−k) for whichHy=0
for any code word y of the linear block code (n, k).
At a receiver, a block decoder is used to estimate the original message based on the received data samples. An input information vector v of length n received by a decoder is said to be related to a code word y of a linear block code (n, k) if it represents the code word y received after a transmission through a noisy channel. The information vector v is also referred to hereafter as a soft information vector, and its elements are referred to as soft values related to code word symbols, or received samples.
A hard decision is said to be taken on an element of a soft information vector if the element is assigned a value of a nearest code symbol by some hard decision rule applied to the modulation symbols. A hard decision vector d related to a soft information vector v is a vector comprised of code symbols in accordance with a certain rule so as to approximate the code word y to which vector v is related.
Known decoding approaches can be divided into two categories distinguished by how they utilize an incoming analogue information stream: these are hard-decision decoding and soft decision decoding. Hard-decision decoders start with input information in a digitized form of code symbols, or “hard decisions”, and use decoding algorithms to attempt to correct any errors that have occurred. Soft-decision decoding (SDD) on the other hand utilizes additional information present in the received data stream. SDD starts with soft decision data that may include hard information indicating which value each received symbol is assigned (e.g. a “1” or a “0” for binary symbols) and an associated value that indicates a reliability or confidence that the value assigned to a particular received symbol is correct. This is generally referred to as “soft input” information. A decoder then utilizes the soft input information to decode the received information so as to produce a code word most likely to represent the original transmitted data.
An approach that estimated the code phase by determining the state of the spreading sequence generator from observations of the spreading sequence was presented in R. B. Ward, “Acquisition of pseudonoise signals by sequential estimation,” IEEE Trans Communication, COM-13, pp. 475-483, December 1965, which is incorporated herein by reference. The algorithm disclosed therein uses the fact that for a linear feedback shift register (LFSR), k chips from the spreading sequence could define the state of the k-stage shift register used to generate the sequence. In the algorithm, k chip hard decisions are made and loaded into a replica of the transmitter's sequence generator in the receiver. The tracking circuit is started and if the k chip decisions were correct, the algorithm will produce the correct sequence and the code phase is acquired. It is determined through correlation whether the local PN sequence is properly aligned. The process of making chip decisions, loading the sequence generator and testing the sequence repeats until code phase is acquired. One disadvantage of this approach is that it requires access to the chip decisions from the channel and thus is unsuitable for signals that are modulated with data. Another disadvantage is that its performance suffers in high noise environments, where chip decisions would have a high probability of error. The algorithm of Ward makes essentially no use of the coding structure available.
A method to acquire the state of a shift register sequence using majority logic decoding was presented in C. C. Kilgus, “Pseudonoise code acquisition majority logic decoding,” IEEE Trans. on Communication, COM-21, No. 6, pp. 772-774, June 1973. It was also recognised that a k-stage LFSR generates a maximum length code with length 2k-1. The algorithm of Kilgus makes a number of hard chip decisions, n, on the spreading sequence. The n chip decisions formed a truncated codeword from the maximum length code. A number of independent estimates were obtained for the bits in the initial state of the shift register. Majority logic was employed on the estimates to provide an estimate on the initial state of the k-stage LFSR that generated the n chips of the spreading sequence. The spreading sequence was treated as an (n,k) code and employed a hard decision majority logic decoder to provide an estimate of the initial state of the shift register. One drawback of the method of Kilgus is that it requires chip decisions for the spreading sequence which can be unavailable if data modulation is present.
Other prior art publications utilize common decoding techniques for code phase acquisition, or to acquire a state of the spreading generator from a received signal; these include H. M. Pearce and M. Ristenblatt, “The threshold decoding estimator for synchronization with binary linear recursive sequences,” ICC'71 Conference Record, pp. 43-25 to 43-30, Jun. 12-14, 1971 Montreal Canada; R. B. Ward and K. P. Yiu, “Acquisition of pscudonoise signals by recursion aided sequential estimation,” TREE Trans. on Communications, COM-25 pp. 784-794, August 1977; G. L. Sather, J. W. Mark, and I. F. Blake, “Sequence acquisition using bit estimation techniques,” Information Science, vol. 32, no. 3, pp. 217-229, 1984; P. Guinand and J. Lodge, “Iterative decoding of truncated simplex codes,” in Proc. of 21st Biennial Symposium on Communications, Kingston, Ont., Jun. 2-5, 2002, pp. 82-85; M. Zhu and K. M. Chugg, “Iterative message passing techniques for rapid code acquisition,” in Proc. IEEE Military Communications Conf., 2003. and K. M. Chugg and M. Zhu, “A New Approach to Rapid PN Code Acquisition using Iterative Message Passing Techniques”, IEEE Journal of Selected Areas in Comm. Vol. 23, No. 5, May 2005, pp. 884-897; O. W. Yeung and K. M. Chugg, “A Low Complexity Circuit Architecture for Rapid PN Code Acquisition in UWB Systems Using Iterative Message Passing on Redundant Graphical Models,” Proceedings of 43rd Allerton Conference on Communication, Control and Computing, September 2005, pp. 698-707; F. Principe, K. M. Chugg and M. Luise, “Rapid Acquisition of Gold Codes and Related Sequences using Iterative Message Passing on Redundant Graphical Models,” Proc. IEEE Military Communications Conf., 2006; L. L. Yang and L. Hanzo, “Iterative soft sequential estimation assisted acquisition of m-sequences,” Electronic Letters, Vol. 38, No. 24, November 2002, pp. 1550-1551 and L. L. Yang and L. Hanzo, “Acquisition of m-Sequences Using Recursive Soft Sequential Estimation,” IEEE Trans. on Communications, Vol. 52, No. 2, February 2004, pp. 199-204. All of these prior art publications disclose solutions that require knowledge of chip decisions for the spreading sequence that was used to generate the DSSS signal, and thus are not suitable for signals that are modulated with data. Another drawback of the aforementioned prior art methods is that they are formulated for BPSK modulation, while many applications of CDMA utilize complex modulation formats such as QPSK. Furthermore, these methods require the knowledge of the carrier phase for the acquisition to be successful.
In an article by L. L. Yang and L. Hanzo, “Differential Acquisition of m-Sequences Using Recursive Soft Sequential Estimation,” IEEE Trans. on Wireless Communications, Vol. 4, No. 1, January 2005, decoding principles were used for the acquisition with a differential operation on consecutive chip samples. The differential operation eliminates the need for accurate carrier phase information and access to the chip decisions, which means it could acquire the sequence in the presence of data modulation. However, the method disclosed by L. L. Yang and L. Hanzo is limited to m-sequence spreading sequences and BPSK modulation.
An object of the present invention is to provide a method and an apparatus for an efficient acquisition of the spreading code of a complex-valued DSSS signal modulated with data.